/LMAR=0/XLINE=3/FONT#0=BASL30/FONT#1=BASB30/FONT#2=NGR25/FONT#3=BASI30/FONT#4=BDR40/FONT#5=NGB25/FONT#6=NGR20/FONT#7=GRFX35/FONT#8=MS25/FONT#9=SUP/FONT#10=SUB






␈↓ α,␈↓∧␈↓ β␈↓ βm␈↓&AM:␈↓)αβ  An Artificial Intelligence Approach to

␈↓ α,␈↓∧␈↓ β␈↓ β]Discovery in Mathematics as Heuristic Search










␈↓ α,␈↓¬␈↓ β␈↓ ε
A DISSERTATION
␈↓ α,␈↓¬␈↓ β␈↓ ∧#SUBMITTED TO THE COMPUTER SCIENCE DEPARTMENT
␈↓ α,␈↓¬␈↓ β␈↓ ∧YAND THE COMMITTEE ON GRADUATE STUDIES
␈↓ α,␈↓¬␈↓ β␈↓ ¬POF STANFORD UNIVERSITY
␈↓ α,␈↓¬␈↓ β␈↓ ∧CIN PARTIAL FULFILLMENT OF THE REQUIREMENTS
␈↓ α,␈↓¬␈↓ β␈↓ ¬vFOR THE DEGREE OF
␈↓ α,␈↓¬␈↓ β␈↓ ¬\DOCTOR OF PHILOSOPHY
















␈↓ α,␈↓↓␈↓ β␈↓ εb␈↓By␈↓↓

␈↓ α,␈↓↓␈↓ β␈↓ ¬↑Douglas  Bruce  Lenat

␈↓ α,␈↓↓␈↓ β␈↓ ε1July,  l976




























␈↓ α,␈↓␈↓ ε∂␈↓λc␈↓ Copyright 1976

␈↓ α,␈↓␈↓ εtby

␈↓ α,␈↓␈↓ ε	Douglas  B.  Lenat


















␈↓ α,␈↓␈↓ εr-␈↓εii␈↓-␈↓ \




␈↓ α,␈↓βI␈αcertify␈αthat␈αI␈αhave␈αread␈αthis␈αthesis␈αand␈αthat␈αin␈αmy␈αopinion␈αit␈αis␈αfully␈αadequate,␈αin␈αscope␈αand
␈↓ α,␈↓β␈↓ β≤quality, as a dissertation for the degree of Doctor of Philosophy.

␈↓ α,␈↓β␈↓ ¬|␈↓&                                                                        ␈↓ R ␈↓)αβ 
␈↓ α,␈↓β␈↓ ¬|␈↓ π≤␈↓εC. Cordell Green (Principal Adviser)␈↓β



␈↓ α,␈↓βI␈αcertify␈αthat␈αI␈αhave␈αread␈αthis␈αthesis␈αand␈αthat␈αin␈αmy␈αopinion␈αit␈αis␈αfully␈αadequate,␈αin␈αscope␈αand
␈↓ α,␈↓β␈↓ β≤quality, as a dissertation for the degree of Doctor of Philosophy.

␈↓ α,␈↓β␈↓ ¬|␈↓&                                                                        ␈↓ R ␈↓)αβ 
␈↓ α,␈↓β␈↓ ¬|␈↓ π≤␈↓εBruce G. Buchanan␈↓β



␈↓ α,␈↓βI␈αcertify␈αthat␈αI␈αhave␈αread␈αthis␈αthesis␈αand␈αthat␈αin␈αmy␈αopinion␈αit␈αis␈αfully␈αadequate,␈αin␈αscope␈αand
␈↓ α,␈↓β␈↓ β≤quality, as a dissertation for the degree of Doctor of Philosophy.

␈↓ α,␈↓β␈↓ ¬|␈↓&                                                                        ␈↓ R ␈↓)αβ 
␈↓ α,␈↓β␈↓ ¬|␈↓ π≤␈↓εEdward A. Feigenbaum␈↓β



␈↓ α,␈↓βI␈αcertify␈αthat␈αI␈αhave␈αread␈αthis␈αthesis␈αand␈αthat␈αin␈αmy␈αopinion␈αit␈αis␈αfully␈αadequate,␈αin␈αscope␈αand
␈↓ α,␈↓β␈↓ β≤quality, as a dissertation for the degree of Doctor of Philosophy.

␈↓ α,␈↓β␈↓ ¬|␈↓&                                                                        ␈↓ R ␈↓)αβ 
␈↓ α,␈↓β␈↓ ¬|␈↓ π≤␈↓εDonald E. Knuth␈↓β



␈↓ α,␈↓βI␈αcertify␈αthat␈αI␈αhave␈αread␈αthis␈αthesis␈αand␈αthat␈αin␈αmy␈αopinion␈αit␈αis␈αfully␈αadequate,␈αin␈αscope␈αand
␈↓ α,␈↓β␈↓ β≤quality, as a dissertation for the degree of Doctor of Philosophy.

␈↓ α,␈↓β␈↓ ¬|␈↓&                                                                        ␈↓ R ␈↓)αβ 
␈↓ α,␈↓β␈↓ ¬|␈↓ π≤␈↓εAllen Newell␈↓β




␈↓ α,␈↓Approved for the University Committee on Graduate Studies:

␈↓ α,␈↓␈↓ ¬|␈↓&                                                                        ␈↓ R ␈↓)αβ 
␈↓ α,␈↓␈↓ ¬|␈↓ π≤␈↓ε(Dean of Graduate Studies)␈↓


␈↓ α,␈↓␈↓ εm-␈↓εiii␈↓-␈↓ \











␈↓ α,␈↓∧␈↓ ¬g␈↓&Acknowledgments␈↓)αβ




␈↓ α,␈↓I␈αowe␈α
a␈αgreat␈αdebt␈α
of␈αthanks␈αto␈α
many␈αpeople,␈α
both␈αfor␈αthe␈α
input␈αof␈αnew␈α
ideas␈αand␈α
for␈αthe
␈↓ α,␈↓evaluation, channelling, and pruning of my own.

␈↓ α,␈↓Let␈αme␈α
begin␈αby␈α
alphabetically␈αthanking␈α
my␈αcommittee:␈α
Bruce␈αBuchanan,␈α
Ed␈αFeigenbaum,
␈↓ α,␈↓Cordell␈αGreen,␈αDon␈αKnuth,␈α
and␈αAllen␈αNewell.␈α Interacting␈αwith␈α
each␈αof␈αthem␈αhas␈α
been␈αan
␈↓ α,␈↓exciting experience, and my thesis has greatly bene≡ted from their guidance.

␈↓ α,␈↓The␈α⊃following␈α⊃individuals␈α⊃have␈α⊃each␈α⊃informally␈α⊃supplied␈α⊃some␈α⊃ideas␈α⊃or␈α⊃comments␈α⊃that
␈↓ α,␈↓appear␈α∪within␈α∀this␈α∪thesis.␈α∪They␈α∀all␈α∪have␈α∪earned␈α∀my␈α∪gratitude,␈α∪and␈α∀have␈α∪signi≡cantly
␈↓ α,␈↓improved␈αthe␈αexperence␈αyou␈αare␈αabout␈αto␈αhave,␈αthat␈αof␈αreading␈αthis␈αthesis:␈αDanny␈αBobrow,
␈↓ α,␈↓Don␈α∂Cohen,␈α∂Avra␈α∞Cohn,␈α∂Randy␈α∂Davis,␈α∞Bob␈α∂Floyd,␈α∂Carl␈α∞Hewitt,␈α∂Earl␈α∂Sacerdoti,␈α∞Richard
␈↓ α,␈↓Weyrauch,␈α∃and␈α∃Terry␈α∃Winograd.␈α∃ Let␈α∃me␈α∃also␈α∃thank␈α∃SAIL,␈α∃SRI,␈α∃and␈α⊗SUMEX␈α∃for
␈↓ α,␈↓providing␈α⊂a␈α∂sophisticated␈α⊂computing␈α⊂environment␈α∂in␈α⊂which␈α⊂to␈α∂work.␈α⊂ This␈α⊂research␈α∂was
␈↓ α,␈↓supported by ARPA contracts


␈↓ α,␈↓Around␈α∞this␈α∞point␈α∞in␈α∞the␈α∞␈↓βAcknowledgements␈↓,␈α∞most␈α∞theses␈α∞have␈α∞some␈α∞sort␈α∞of␈α∞tribute␈α∞to␈α
the
␈↓ α,␈↓candidate's␈α∞wife.␈α∂Until␈α∞I␈α∞was␈α∂in␈α∞the␈α∞throes␈α∂of␈α∞this␈α∞research,␈α∂I␈α∞never␈α∞fully␈α∂appreciated␈α∞the
␈↓ α,␈↓importance␈α∪of␈α∩such␈α∪support.␈α∩ So␈α∪let␈α∪me␈α∩sincerely␈α∪acknowledge␈α∩the␈α∪indispensable␈α∪aid␈α∩I
␈↓ α,␈↓received␈α
from␈α
Merle,␈αmy␈α
wonderful␈α
wife,␈αwho␈α
put␈α
up␈α
with␈αinverted␈α
schedules␈α
and␈αwho␈α
gave
␈↓ α,␈↓me the con≡dence to tackle this problem and the enthusiasm to keep going.













␈↓ α,␈↓␈↓ εn-␈↓εiv␈↓-␈↓ \

␈↓ α,␈↓␈↓ β␈↓ ¬S␈↓∧␈↓&Table of Contents␈↓)αβ␈↓


















































␈↓ α,␈↓␈↓ εr-␈↓εv␈↓-␈↓ \


␈↓ α,␈↓∧␈↓ β⎇␈↓&AM:␈↓)αβ  An Artificial Intelligence Approach to
␈↓ α,␈↓∧␈↓ βmDiscovery in Mathematics as Heuristic Search

␈↓ α,␈↓↓␈↓ ¬dDouglas B. Lenat, Ph.D.
␈↓ α,␈↓↓␈↓ ¬[Stanford University, l976



␈↓ α,␈↓A␈α
program,␈α
called␈α
"AM",␈α
is␈α
described␈αwhich␈α
models␈α
one␈α
aspect␈α
of␈α
elementary␈αmathematics

␈↓ α,␈↓research: developing new concepts under the guidance of a large body of heuristic rules.


␈↓ α,␈↓The␈αlocal␈αheuristics␈αcommunicate␈αvia␈αan␈α
agenda␈αmechanism,␈αwhich␈αis␈αa␈αglobal␈αlist␈α
of␈αtasks

␈↓ α,␈↓for␈α
the␈α
system␈α
to␈α
perform␈α
and␈α
reasons␈α
why␈α
each␈α
task␈α
is␈α
plausible.␈α
 A␈α
single␈α
task␈αmight␈α
direct

␈↓ α,␈↓AM␈αto␈αde≡ne␈αa␈αnew␈αconcept,␈αor␈αto␈αexplore␈αsome␈αfacet␈αof␈αan␈αexisting␈αconcept,␈αor␈αto␈αexamine

␈↓ α,␈↓some␈α
empirical␈α
data␈α∞for␈α
regularities,␈α
etc.␈α
 The␈α∞program␈α
repeatedly␈α
selects␈α
from␈α∞the␈α
agenda

␈↓ α,␈↓the task having the best supporting reasons, and then executes it.


␈↓ α,␈↓Each␈α∪concept␈α∩is␈α∪an␈α∪active,␈α∩structured␈α∪knowledge␈α∪module.␈α∩ A␈α∪hundred␈α∪very␈α∩incomplete

␈↓ α,␈↓modules␈α∀are␈α∀initially␈α∃provided,␈α∀each␈α∀one␈α∃corresponding␈α∀to␈α∀an␈α∃elementary␈α∀set-theoretic

␈↓ α,␈↓concept␈α∂(e.g.,␈α∞union).␈α∂ This␈α∞provides␈α∂a␈α∞de≡nite␈α∂but␈α∞immense␈α∂"space"␈α∞which␈α∂AM␈α∂begins␈α∞to

␈↓ α,␈↓explore.␈α⊂ AM␈α⊂extends␈α⊂its␈α⊂knowledge␈α⊂base,␈α⊂ultimately␈α⊂rediscovering␈α⊂hundreds␈α⊂of␈α⊂common

␈↓ α,␈↓concepts (e.g., numbers) and theorems (e.g., unique factorization).


␈↓ α,␈↓This approach to plausible inference contains great powers and great limitations.



␈↓ α,␈↓¬␈↓ λ<Approved for publication:

␈↓ α,␈↓¬␈↓ λ<By ␈↓&                                    ␈↓ R ␈↓)αβ
␈↓ α,␈↓¬␈↓ λ<␈↓ 	\␈↓εFor Major Department␈↓¬

␈↓ α,␈↓¬␈↓ λ<By ␈↓&                                    ␈↓ R ␈↓)αβ
␈↓ α,␈↓¬␈↓ λ<␈↓ 	\␈↓εDean of Graduate Studies␈↓¬
␈↓ α,␈↓␈↓εAppendix ␈↓ ¬¬␈↓↓AM  ␈↓ε Discovery in Mathematics as Heuristic Search␈↓ ;␈↓-␈↓ε3␈↓-

␈↓ α,␈↓␈↓ ∧S␈↓↓␈↓&Appendix .. ␈↓)αβ␈↓∧␈↓&Index to Initial Concepts␈↓)αβ␈↓↓



␈↓ α,␈↓∧␈↓&CONCEPT␈↓)αβ␈↓ ¬|␈↓&PAGE␈↓)αβ     ␈↓&CONCEPT␈↓)αβ␈↓ 
q␈↓&PAGE␈↓)αβ


␈↓ α,␈↓␈↓ ¬g␈↓∧␈↓&Things still to do␈↓)αβ␈↓